/* =========================================================================================
PROJET           : c-social-network
NOM DU FICHIER   : algo.h
OBJET            : Module algo
--------------------------------------------------------------------------------------------
DATE DE CREATION : 07/05/10
AUTEUR           : Joris PUECHLONG
--------------------------------------------------------------------------------------------
MODIFICATIONS (   n) date - auteur - description )
	1) 07/05/2010 - JORIS puechlong - Reflexion, debut codage
	2) 09/05/2010 - JORIS puechlong - codage
	3) 17/05/2010 - Benjamin MICHEL - revision de l'algo CFC, et de l'algo parcours
	4) 18/05/2010 - Benjamin MICHEL - get_all_cfc, next_cfc
	5) 20/05/2010 - Benjamin MICHEL - commence écriture get_chemin

========================================================================================= */

#include <stdio.h>
#include <stdlib.h>

#include "algo.h"

/*==============================================
DECLARATION FONCTION PRIVEES
==============================================*/


/*
procedure next_cfc(IN OUT: t_graph* graph);
fait en sorte que toutes les personnes de graph marquees deviennent vus.

--require:
--   le graph non vide
--ensure:
--  les personnes de graph qui etaient marquees son a present vus
*/
void next_cfc(t_graph *);


/*
parcours les personnes que l'on peut qtteindre a partir de la personne donnee en parametre
données: pointeur sur personne
résultat: les personnes par lesquelles nous somme passées sont marquees

--require:
--  La personne donnee en parametre existe
--ensure:
--  toutes les personnes atteignable a partir de la personne donnee en parametre seront marquees
*/
void parcours(  t_personne *);


/*
C'est pas plutot que la composante connexe (pas fortement)?
Calcul d'une composante fortement connexe du graphe g contenant la personne x
données: un pointeur sur une personne
données: un pointeur sur le graph
données: un pointeur sur le graph dual
resultat: un pointeur sur une liste de personnes

--require:
--  La liste de personnes doit etre vide lorsqu'elle est passee en parametre
--  Les deux graphs doivent contenir les memes personnes, et ils doivent etre dual reciproquement
--  La personne doit appartenire a un graph (par consequent aux deux)
--ensure:
--  tous les points de la liste fournie appartiennent aux deux graphs
*/
void CFC( t_graph *, t_graph *, t_personne *, t_liste **);


/*
function get_min(IN: t_liste *)return t_personne;
*/
t_personne* get_min(t_liste **);

void pile( t_personne *, t_personne *, t_liste **);

/*==============================================
FIN
==============================================*/

void parcours( t_personne *pers){
	/*==================================================
	Initialisations
	====================================================*/

    t_liste *liste = NULL;/*une liste de personnes*/

	/*==================================================
	Execution
	====================================================*/
	/*on copie la liste de personnes en qui la personne fait confiance*/
    liste = f_personne.get_conf(pers);
    /*boucler tant que la liste n'est pas vide*/
    while( !f_liste.is_vide(liste) ){
        /*si la première personne n'a jamais été atteinte*/
        if( !f_personne.is_marque(f_liste.get_pers(liste)) ){
            /*marquer la personne*/
            f_personne.marque( f_liste.get_pers(liste) );
            /*lancer une parcours sur cette personne*/
            parcours( f_liste.get_pers(liste) );
        }
        /*passer à la personne suivante*/
        liste = f_liste.get_next(liste);
    }/*on ne fait plus de recursion quand toute les personnes de la composante connexe ont ete marquees*/
    /*détruire la liste*/
    f_liste.destroy(&liste);
}


void CFC( t_graph *graph, t_graph *graph_d, t_personne *pers, t_liste **liste ){
	/*==================================================
	Initialisations
	====================================================*/
	int i;/*iteration*/
    t_personne *pers_d = NULL;/*pers dans le graph dual*/
    t_personne *pers_temp = NULL;/*une personne du graph pour les vérifications*/
    t_personne *pers_temp_d = NULL;/*une personne du graph dual pour les vérifications*/

	/*==================================================
	Execution
	====================================================*/

	/*Penser a mettre une fonction qui marque toute les personnes comme non atteintes*/
	next_cfc(graph_d);
	next_cfc(graph);

    /*on récupère la composante connexe de pers*/
	
	/*On marque la personne de depart*/
	f_personne.marque( pers );
    parcours( pers );
    /*on récupère pers dans le graph dual*/
    pers_d = f_graph.get_pers( graph_d, f_personne.get_id(pers) );
	/*On marque la personne de depart*/
	f_personne.marque( pers_d );
    /*on récupère les composantes connexed de pers_d*/
    parcours( pers_d );

    /*on vérifie pour chaque personnes si elles sont marquées dans les deux graphs*/
    for(i = 0; i < f_graph.get_taille( graph ); i++){
        /*récupérer la même personne dans les deux graphs*/
        pers_temp = f_graph.get_pers_num(graph, i);
        pers_temp_d = f_graph.get_pers_num(graph_d, i);
        /*on vérifie que la personne est atteinte dans les deux graphs*/
        if( f_personne.is_marque(pers_temp) && f_personne.is_marque(pers_temp_d) ){
            f_liste.ajout_pers(liste, pers_temp);/*on ajoute la personne dans la composante fortement connexe*/
		}else if( f_personne.is_marque(pers_temp) || f_personne.is_marque(pers_temp_d) ){
			/*marquer la personne comme si elle n'avait jamais ete rencontree*/
            f_personne.marque_nouv( pers_temp );
			f_personne.marque_nouv( pers_temp_d );
		}
    }
    /*la liste est modifiée, et elle contient tout les éléments de la composante fortement connexe*/
}

void next_cfc(t_graph *graph){
	/*==================================================
	Initialisations
	====================================================*/
	int i;/*iteration*/
	t_personne *pers_temp;/*une personne dans le graph*/
	/*==================================================
	Execution
	====================================================*/
	/*pour toute les personnes du graph*/
	for( i = 0; i < f_graph.get_taille(graph); i++){
		pers_temp = f_graph.get_pers_num(graph, i);/*récupère la personne*/
		if (f_personne.is_marque(pers_temp))/*si la personne est marquée*/
			f_personne.marque_vu(pers_temp);/*marquer la personne comme vue*/
	}
}


t_personne* get_min(t_liste **liste_pers){
	int min;/*valeur minimale*/
	t_personne *pers_temp;/*personne la plus proche*/
	t_liste *liste_t = *liste_pers;
	printf("\ntest2.1.0\n");
	/*on prend la distance de la source + celle de la premiere valeur*/
	printf("\ntest2.1.0res=%d\n", f_personne.get_frequence( f_liste.get_pers(liste_t) ));
	min = f_personne.get_distance( f_liste.get_pers(liste_t) ) ;
	printf("\ntest2.1.0res=%d_min=%d\n", f_personne.get_frequence( f_liste.get_pers(liste_t) ), min);
	pers_temp = f_liste.get_pers(liste_t);
	printf("\n\t%d", f_personne.get_id(f_liste.get_pers(*liste_pers)));
	/**/
	while( !f_liste.is_vide(liste_t) ){
		if( min >= f_personne.get_frequence( f_liste.get_pers(liste_t) ) ){
			min = f_personne.get_frequence( f_liste.get_pers(liste_t) );
			pers_temp = f_liste.get_pers(liste_t);
			printf("\ntest2.1.0res=%d\n", f_personne.get_id(pers_temp));
			printf("\ntest2.1.1_in\n");
		}
		printf("\ntest2.1.3\n");
		/*passage a la personne suivante*/
		liste_t = f_liste.get_next(liste_t);
		printf("\ntest2.1.4\n");
	}
	printf("\ntest2.1.5\n");
	printf("\n\t%d", f_personne.get_id(f_liste.get_pers(*liste_pers)));
	f_liste.pop_pers(pers_temp, liste_pers);
	/******/
	printf("\n\t%d", f_personne.get_id(f_liste.get_pers(*liste_pers)));
	printf("\ntest2.1.5res=%d\n", f_personne.get_id( f_liste.get_pers(*liste_pers) ));
	printf("\ntest2.1.fin\n");
	return pers_temp;
}

void source_uniq_init(t_graph *graph, t_personne *origine){
	int i;/*iteration*/	
	/*initialisation de tout les elements du graph*/	
	for (i = 0; i < f_graph.get_taille(graph); i++){
		f_personne.set_pere(
			f_graph.get_pers_num(graph, i),
			NULL
		);
		f_personne.set_distance(
			f_graph.get_pers_num(graph, i),
			-1
		);
	}
	f_personne.set_distance(origine, 0);
}

void relacher(t_personne *origine, t_personne *destination){
	/*si on n'a jamais donne de distance opu si celle ci est plus grande que maintenant*/
	if(	(f_personne.get_distance(destination) == -1) ||
		(f_personne.get_distance(destination) > f_personne.get_distance(origine) + f_personne.get_frequence(destination)) ){
		/*donne une nouvelle distance*/
		f_personne.set_distance(
			destination,
			f_personne.get_distance(origine) + f_personne.get_frequence(destination)
		);
		f_personne.set_pere(
			destination,
			origine
		);
	}
}
void pile( t_personne *pers_end, t_personne *pers_beg, t_liste **chemin ){
	if (f_personne.get_pere(pers_end) != pers_beg)
		pile( f_personne.get_pere(pers_end), pers_beg, chemin );
	f_liste.ajout_pers(chemin, pers_end);
}

/*====================================================
FONCTION PUBLIQUES
====================================================*/

static int GET_ALL_CFC( t_graph *graph, t_graph *graph_d, t_liste *** tab_liste){
	/*==================================================
	Initialisations
	====================================================*/
    int i;/*iteration*/
    int j = 0;/*compte le nombre de composantes connexes*/
	t_liste **liste_pers = NULL;/*tab_liste est un tableau contenant les composantes fortement connexes
	tableau de pointeurs*/

	/*==================================================
	Execution
	====================================================*/
    /*pour toute les personnes du graph*/
	for( i = 0; i < f_graph.get_taille(graph); i++){
		if(!f_personne.is_vu( f_graph.get_pers_num(graph, i) )){/*si la personne est non marquée*/
		    liste_pers = realloc(liste_pers, sizeof(t_liste **) * (j+1));/*on alloue un espace en plus*/
		    liste_pers[j] = f_liste.creer();/*creer une liste de personnes*/
			CFC(
                graph,/*le graph*/
                graph_d,/*le graph dual*/
                f_graph.get_pers_num(graph, i), /*la personne du graph*/
                &(liste_pers[j]) /*la composante connexe de la personne
				&liste_temp*/
            );/*on calcul sa composante connexe*/
            j++;/*on passe a la composante connexe suivante*/
		}
	}
	*tab_liste = liste_pers;/*on passe les composantes fortement connexes*/
	return j;
}

static t_liste * GET_CHEMIN( t_personne * pers_start, t_personne * pers_end, t_graph *graph){
	/*==================================================
	Initialisations
	====================================================*/
	int i;/*iteration*/
	t_liste *chemin = NULL;/*le chemin emprunté pour aller de pers_start à pers_end*/
	t_liste *liste_t = NULL;/*Une liste de valeurs temporaires*/
	t_liste *liste_t_rel = NULL; /*Une liste temporaire pour le relachement*/
	t_personne *pers_temp = NULL;
	/*==================================================
	Execution
	====================================================*/
	printf("\ntest2.0\n");
	source_uniq_init(graph, pers_start);
	liste_t = f_liste.creer();
	printf("\ntest2.1\n");
	
	/*mettre tout les points du graph dans liste_t*/
	for(i = 0; i < f_graph.get_taille(graph) ; i++){
		f_liste.ajout_pers(&liste_t, f_graph.get_pers_num(graph, i));
	}

	
	while( !f_liste.is_vide(liste_t) ){
		printf("\ntest2.1res=%d\n", f_personne.get_id(f_liste.get_pers(liste_t)));
		pers_temp = get_min(&liste_t);
		printf("\ntest2.2res=%d\n", f_personne.get_id(f_liste.get_pers(liste_t)));
		liste_t_rel = f_personne.get_conf(pers_temp);
		printf("\ntest2.2res=%d\n", f_personne.get_id(f_liste.get_pers(liste_t)));
		while ( !f_liste.is_vide(liste_t_rel) ){/*on fait le relachement sur tout les successeurs de pers_temp*/
			relacher(pers_temp, f_liste.get_pers(liste_t_rel));
			liste_t_rel = f_liste.get_next(liste_t_rel);
		}
	}
	printf("\ntest2.4\n");
	/*retrouve la personne avec l'aide d'une pile*/
	pile(pers_end, pers_start, &chemin);
	printf("\ntest2.FIN\n");
	return chemin;
}

/*====================================================
END
====================================================*/


/*
initialisation de la structure f_algo pour usage externe
*/
struct _ALGO f_algo = {
    GET_ALL_CFC, GET_CHEMIN
};
